package imooc_math.sort;

public class QuickSort3Way {
	
	public static void sort(Comparable[] arry,int l,int r){
		
		if(l>=r){
			return;
		}
		int lt=l;
		int gt=r+1;
		Object v=arry[l];
		int i=l+1;
		//[l+1,lt]<n	[lt+1,i-1]=n	[gt,r]>n
		while(i<gt){//
			if(arry[i].compareTo(v)<0){
				lt++;
				swap(arry,lt,i);
				System.out.println();
				i++;
			}else if(arry[i].compareTo(v)==0){
				i++;
			}else if(arry[i].compareTo(v)>0){
				gt--;
				swap(arry,i,gt);
				//i++;
			}
		}
		swap(arry,l,lt);//此时小于v的下标范围是[l,lt-1],下标为lt的值为v
		sort(arry,l,lt-1);
		sort(arry,gt,r);
	}
	public static void sort(Comparable[] arry){
		int n=arry.length;
		sort(arry,0,n-1);
		
	}
	public static void swap(Object [] arr,int a,int b){
		Object t=arr[a];
		arr[a]=arr[b];
		arr[b]=t;
	}
	
}
